package main

import (
	"math"
	"strings"
)

// 3.无重复字符的最长子串
func main() {
	//nums := []int{-1, 0, 1, 2, -1, -4}
	//str := "abcabcbb"
	//str := "bbbbb"
	str := "pwwkew"
	res := lengthOfLongestSubstring2(str)
	println(res)
}

func lengthOfLongestSubstring2(s string) int {
	// 解法2：滑动窗口，使用一个Map或者Set来记录当前窗口的数据
	// 遍历到当前元素时，看看是否过去有过这个元素，有的话，逐个按照下标删除已有的元素，直到当前元素不存在于集合中
	maxLength := 0
	chars := strings.Split(s, "")
	cursor := 0
	charMap := make(map[string]string)

	for _, c := range chars {
		_, exists := charMap[c]
		for exists {
			delete(charMap, chars[cursor])
			cursor++
			_, exists = charMap[c]
		}
		charMap[c] = c
		maxLength = int(math.Max(float64(len(charMap)), float64(maxLength)))
	}
	return maxLength
}

func lengthOfLongestSubstring(s string) int {
	// 解法1：题解思路 双指针
	// 找每个字符前面对应的相同字符，找到后，前面的部分就是当前的最长字符
	// 设置偏移量，下次就不要找这个字符的前面的部分了，已经重复了，下次就从这个偏移量后面开始找
	chars := strings.Split(s, "")
	leftIndex, maxLength := 0, 0
	for idx, c := range chars {
		for l := leftIndex; l < idx; l++ {
			if chars[l] == c {
				maxLength = int(math.Max(float64(idx-leftIndex), float64(maxLength)))
				leftIndex = idx + 1
				break
			}
		}
	}

	return int(math.Max(float64(maxLength), float64(len(chars)-leftIndex)))
}

//给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
//
//
//
//示例 1:
//
//输入: s = "abcabcbb"
//输出: 3
//解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//示例 2:
//
//输入: s = "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
//示例 3:
//
//输入: s = "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
//
//
//提示：
//
//0 <= s.length <= 5 * 104
//s 由英文字母、数字、符号和空格组成
